1. Field of the Invention
The present invention relates generally to computer drawings, and in particular, to a method, system, apparatus, and article of manufacture for placing annotations in a drawing using simulated annealing.
2. Description of the Related Art
Computer aided design (CAD)/drawing applications often create two-dimensional (2D) schematic documents/drawings of a three-dimensional (3D) model that may then be used for construction, installation, and other applications. Often times, 2D drawings contain geometry and numerous labels for such geometry (e.g., dimension labels, names, description, area, group, reference pipe network and structure, reference surface, identifying information, etc.). Labels need to be placed in a manner that creates a clean easily readable document. Unfortunately, prior art systems failed to provide a mechanism for placing labels that would result in a clean easily readable document. To better understand these problems, a description of prior art label placement systems may be useful.
Prior art label placement systems employ a greedy method to place annotations one at a time at an open location (e.g., that didn't collide with another label). Such a greedy method leads to space starvation for subsequently placed annotations/labels and needless intersections because the greedy system cannot move previously placed annotations. FIG. 1 illustrates the results of label placement using a greedy method in the prior art. As can be seen, labels 102, 104, 106, and 108 have leaders 110, 112, 114, and 116 (i.e., lines connecting the labels to the associated object/item in the drawing) respectively that intersect and create a cluttered view of the drawing 100.
As an example of the prior art, if one hundred (100) labels are to be placed in the drawing, the greedy method would go through each label and find an open location that didn't collide with other labels/leaders. However, as the labels are placed, there is no ability to move a previously placed label to find a better placement. Thus, the first ninety-nine (99) labels may not intersect and take up space, but trying to find a suitable location for the one-hundredth (100th) label without moving the first ninety-nine (99) labels was not possible. In other words, as the label placement process continues from zero (0) to n labels, the placement of later labels is less and less optimal due to the consumption of available space by already placed labels.